Navigation systems can employ routing algorithms to determine a route from an origin to a destination. Routing algorithms can be applied to map data to determine a desired route from an origin to a destination. The map data can include information regarding the locations of travel segments (e.g. streets, transit routes, or other traversable paths), connections between the segments, and costs of transitioning between the segments. The map data can be modeled using a graph model where each vertex or node in the graph model represents a travel segment and each arc or edge between the vertices represents a transition between travel segments.
Routing algorithms can compute paths through the graph model (e.g. using Dijkstra's algorithm) to calculate a route from origin to destination based on metrics (e.g. distance, time, etc.). Example routing algorithms can employ various techniques to facilitate determination of a path in the graph model. For example, a contraction hierarchies process can be used to speed up the route calculation by precomputing a hierarchical order of vertices and constraining the route search to increasingly more important vertices towards the middle of the route. Other example routing algorithms can speed up route computation using, for instance, vertex reach.